
/*
       	mm.c
        
        Implementation of memory management
        
        Meng Sun(c) leon.meng.sun@gmail.com
        Source code released under LGPLv3
        https://www.gnu.org/licenses/lgpl-3.0.txt
*/

#include "mm.h"

static MemoryPageDescriptor* mpdFreeListHead = NULL;
static MemoryPageDescriptor* mpdUsedListHead = NULL;

static DynamicObjectDescriptor* dodFreeListHead = NULL;
static DynamicObjectDescriptor* dodUsedListHead = NULL;

static uint8 tlbTableIndex = 0;

MemoryPageDescriptor** mmGetSystemFreeMPDListHeadPtr(void){
	return &mpdFreeListHead;
}

MemoryPageDescriptor** mmGetSystemUsedMPDListHeadPtr(void){
	return &mpdUsedListHead;
}

DynamicObjectDescriptor** mmGetSystemFreeDODListHeadPtr(void){
	return &dodFreeListHead;
}

DynamicObjectDescriptor** mmGetSystemUsedDODListHeadPtr(void){
	return &dodUsedListHead;
}

public sint8 mmAppendDODToList(DynamicObjectDescriptor* obj, DynamicObjectDescriptor** head){
	
	if (obj == NULL) return -1;
	
	if (*head == NULL){
		obj->prev = NULL;
		obj->next = NULL;
		*head = obj;
	}else{
		obj->prev = NULL;
		obj->next = *head;
		(*head)->prev = obj;
		*head = obj;
	}
	
	return 0;
}

public sint8 mmRemoveDODFromList(DynamicObjectDescriptor* obj, DynamicObjectDescriptor** head){

	if ((obj == NULL) || (*head == NULL)) return -1;
	
	if ((obj->prev == NULL) && (obj->next == NULL)){ /*solo obj*/
		*head = NULL;
	}else if ((obj->prev == NULL) && (obj->next != NULL)){ /*first obj*/
		*head = obj->next;
		obj->next = NULL;
		(*head)->prev = NULL;
	}else if ((obj->prev != NULL) && (obj->next == NULL)){ /*last obj*/
		obj->prev->next = NULL;
		obj->prev = NULL;
	}else{ /*in the middle*/
		obj->prev->next = obj->next;
		obj->next->prev = obj->prev;
		obj->next = NULL;
		obj->prev = NULL;
	}
	
	return 0;
}

sint8 mmAppendMPDToList(MemoryPageDescriptor* obj, MemoryPageDescriptor** head){
	
	if (obj == NULL) return -1;
	
	if (*head == NULL){
		obj->prev = NULL;
		obj->next = NULL;
		*head = obj;
	}else{
		obj->prev = NULL;
		obj->next = *head;
		(*head)->prev = obj;
		*head = obj;
	}
	
	return 0;
}

sint8 mmRemoveMPDFromList(MemoryPageDescriptor* obj, MemoryPageDescriptor** head){

	if ((obj == NULL) || (*head == NULL)) return -1;
	
	if ((obj->prev == NULL) && (obj->next == NULL)){ /*solo obj*/
		*head = NULL;
	}else if ((obj->prev == NULL) && (obj->next != NULL)){ /*first obj*/
		*head = obj->next;
		obj->next = NULL;
		(*head)->prev = NULL;
	}else if ((obj->prev != NULL) && (obj->next == NULL)){ /*last obj*/
		obj->prev->next = NULL;
		obj->prev = NULL;
	}else{ /*in the middle*/
		obj->prev->next = obj->next;
		obj->next->prev = obj->prev;
		obj->next = NULL;
		obj->prev = NULL;
	}
	
	return 0;
}

sint8 mmCopyData(byte* src, byte* dst, uint32 size, bool clear){
	
	uint32 index;
	
	if((src == NULL) || (dst == NULL)) return -1;
	
	if (size == 0) return 0;
	
	for (index = 0; index < size; ++index){
		dst[index] = src[index];
		if (clear == TRUE) src[index] = 0;
	}
	
	return size;
}

static bool mmCheckDODFromList(DynamicObjectDescriptor* dod, DynamicObjectDescriptor* dodListHead){
	
	DynamicObjectDescriptor* dodIndex = dodListHead;
	
	if ((dod == NULL) || (dodIndex == NULL)) return FALSE;
	
	do{
		if (dod == dodIndex){
			return TRUE;
		} else {
			dodIndex = dodIndex->next;
		}
	}while(dodIndex != NULL);
	
	return FALSE;
}

static uint8 mmMMUSize(void){

	uint32 cpval;
	
	ReadCP0Value(cpval, 16, 1);
	return (uint8)((cpval >> 25) & 0x3f) + 1;
}

uint8 mmGetNextTLBTableIndex(void){
	tlbTableIndex = (++tlbTableIndex) % mmMMUSize();
	return tlbTableIndex;
}

sint8 mmGetTLBItemFromMemoryPageDescriptor(TLBItem* tlbItem, MemoryPageDescriptor* mpd, uint8 processID, MemoryCacheType c, MemoryGlobalType g, MemoryWriteType d, MemoryValidType v){

	if (mpd == NULL) return -1;
	if (tlbItem == NULL) return -2;
	
	tlbItem->pageMask = ((mpd->size - 1) & 0xffff) << 13; /*numerically equals*/
	tlbItem->entryLo0 = (((uint32)(mpd->pmaStart) >> 6) & 0x3fffffc0) | (((uint32)c << 3) & 0x38) | (((uint32)d << 2) & 0x4) | (((uint32)v << 1) & 0x2) | ((uint32)g & 0x1);
	tlbItem->entryLo1 = ((((uint32)(mpd->pmaStart) + mpd->size << 12) >> 6) & 0x3fffffc0) | (((uint32)c << 3) & 0x38) | (((uint32)d << 2) & 0x4) | (((uint32)v << 1) & 0x2) | ((uint32)g & 0x1);
	tlbItem->entryHi = ((uint32)(mpd->vmaStart) & 0xffffe000) | ((processID) & 0xff);
	
	return 0;
}

static void callback mmMemorySyscallISRCallback(reg32b cause, uint32* fp, SyscallDescriptor* scd, SyscallReturnDescriptor* scrd){

	switch (scd->cmd){

		case SYSCMDSYSMALLOC: /*mmSysMAlloc*/

			if ((scd == NULL) || (scrd == NULL)) return;
			
			scrd->payload.sysmallocRetPtr = mmSysMAlloc(scd->payload.sysmallocSize);
			
			if (scrd->payload.sysmallocRetPtr == NULL){
				scrd->ifSuccess = FALSE;
			} else {
				scrd->ifSuccess = TRUE;
			}
			
			break;

		case SYSCMDSYSFREE: /*mmSysMFree*/
		
			if ((scd == NULL) || (scrd == NULL)) return;
			
			scrd->payload.sysfreeRetVal = mmSysMFree(scd->payload.sysfreePtr);
			
			if (scrd->payload.sysfreeRetVal == 0){
				scrd->ifSuccess = TRUE;
			} else {
				scrd->ifSuccess = FALSE;
			}
			
			break;

		default:
			break;
	};
	
	return;
}

void mmInit(void){

	uint8 mmuTLBIndex;
	TLBItem tlbItem;
	MemoryPageDescriptor initMPDFree;
	MemoryPageDescriptor initMPDUsed;
	DynamicObjectDescriptor initDODForMPDFree;
	DynamicObjectDescriptor initDODForMPDUsed;
	DynamicObjectDescriptor initDODFree;
	
	/*1.1 init tlb table*/
	tlbItem.entryHi = KSEG0BASEADDR;
	tlbItem.pageMask = 0x0;
	tlbItem.entryLo0 = 0x0;
	tlbItem.entryLo1 = 0x0;
	
	for (mmuTLBIndex = 0; mmuTLBIndex < mmMMUSize(); ++mmuTLBIndex){
		WriteTLBItemByGivenIndex(mmuTLBIndex, tlbItem);
		tlbItem.entryHi += SYSTEMPAGESIZE;
	}
	
	/*1.2 init descriptors*/
	initDODForMPDUsed = (DynamicObjectDescriptor){
		(byte*)0x80500000 + sizeof(DynamicObjectDescriptor),
		sizeof(MemoryPageDescriptor),
		NULL, NULL
	};
	initMPDUsed = (MemoryPageDescriptor){
		(byte*)0x00500000,
		(byte*)0x80500000,
		0x1, NULL, NULL
	};
	initDODForMPDFree = (DynamicObjectDescriptor){
		(byte*)0x80500000 + 2 * sizeof(DynamicObjectDescriptor) + sizeof(MemoryPageDescriptor),
		sizeof(MemoryPageDescriptor),
		NULL, NULL
	};
	initMPDFree = (MemoryPageDescriptor){
		(byte*)0x00502000,
		NULL,
		0x4ff, NULL, NULL
	};
	initDODFree = (DynamicObjectDescriptor){
		(byte*)0x80500000 + 3 * sizeof(DynamicObjectDescriptor) + 2 * sizeof(MemoryPageDescriptor),
		SYSTEMPAGESIZE - 3 * sizeof(DynamicObjectDescriptor) - 2 * sizeof(MemoryPageDescriptor),
		NULL, NULL
	};

	/*1.3 copy descriptors - wired map from 0x80500000->0x00500000*/
	mmCopyData((byte*)(&initDODForMPDUsed), (byte*)0x80500000, sizeof(DynamicObjectDescriptor), FALSE);
	mmCopyData((byte*)(&initMPDUsed), initDODForMPDUsed.start, sizeof(MemoryPageDescriptor), FALSE);
	mmCopyData((byte*)(&initDODForMPDFree), (byte*)0x80500000 + sizeof(DynamicObjectDescriptor) + sizeof(MemoryPageDescriptor), sizeof(DynamicObjectDescriptor), FALSE);
	mmCopyData((byte*)(&initMPDFree), initDODForMPDFree.start, sizeof(MemoryPageDescriptor), FALSE);
	mmCopyData((byte*)(&initDODFree), (byte*)0x80500000 + 2 * sizeof(DynamicObjectDescriptor) + 2 * sizeof(MemoryPageDescriptor), sizeof(DynamicObjectDescriptor), FALSE);

	/*1.4 link to list*/
	mmAppendDODToList((DynamicObjectDescriptor*)0x80500000, &dodUsedListHead);
	mmAppendDODToList((DynamicObjectDescriptor*)((byte*)0x80500000 + sizeof(DynamicObjectDescriptor) + sizeof(MemoryPageDescriptor)), &dodUsedListHead);
	mmAppendDODToList((DynamicObjectDescriptor*)((byte*)0x80500000 + 2 * sizeof(DynamicObjectDescriptor) + 2 * sizeof(MemoryPageDescriptor)), &dodFreeListHead);
	mmAppendMPDToList((MemoryPageDescriptor*)(initDODForMPDUsed.start), &mpdUsedListHead);
	mmAppendMPDToList((MemoryPageDescriptor*)(initDODForMPDFree.start), &mpdFreeListHead);
	
	/*1.5 set memory syscall handler*/
	setMemorySyscallISRCallback(mmMemorySyscallISRCallback);
	
	return;
}

static MemoryPageDescriptor* mmSysPAlloc(void){
	
	DynamicObjectDescriptor dodNewPage;
	MemoryPageDescriptor mpdNewPage;
	DynamicObjectDescriptor dodFreeArea;
	
	MemoryPageDescriptor* freePageListIndex = mpdFreeListHead;
	
	if (freePageListIndex == NULL) return NULL; /*memory exhausted*/

	do{
		if (freePageListIndex->size >= 0x1){ /*free page found*/
		
			/*1.1 reduce free mpd size by 1*/
			freePageListIndex->size -= 0x1;
			
			/*1.2 check if free mpd has perfect fit or has more spaces than needed*/
			if (freePageListIndex->size == 0x0){ /*mpd perfect fit*/
			
				/*1.2.1 update freePageListIndex to new alloc page descriptor*/
				freePageListIndex->size = 0x1;
				freePageListIndex->vmaStart = freePageListIndex->pmaStart + KSEG0BASEADDR;
				
				/*1.2.2 construct free dod for new page*/
				dodFreeArea = (DynamicObjectDescriptor){freePageListIndex->vmaStart + sizeof(DynamicObjectDescriptor), SYSTEMPAGESIZE - sizeof(DynamicObjectDescriptor), NULL, NULL};
				
				/*1.2.3 copy to location*/
				mmCopyData((byte*)(&dodFreeArea), freePageListIndex->vmaStart, sizeof(DynamicObjectDescriptor), FALSE);
				
				/*1.2.4 link*/
				mmRemoveMPDFromList(freePageListIndex, &mpdFreeListHead);
				mmAppendMPDToList(freePageListIndex, &mpdUsedListHead);
				mmAppendDODToList((DynamicObjectDescriptor*)(freePageListIndex->vmaStart), &dodFreeListHead);
				
				/*1.2.5 return*/
				return freePageListIndex;
			}else{ /*mpd has more free spaces than needed*/
			
				/*1.2.1 construct new page descriptors*/
				dodNewPage = (DynamicObjectDescriptor){freePageListIndex->pmaStart + KSEG0BASEADDR + sizeof(DynamicObjectDescriptor), sizeof(MemoryPageDescriptor), NULL, NULL};
				mpdNewPage = (MemoryPageDescriptor){freePageListIndex->pmaStart, freePageListIndex->pmaStart + KSEG0BASEADDR, 0x1, NULL, NULL};
				dodFreeArea = (DynamicObjectDescriptor){mpdNewPage.vmaStart + 2 * sizeof(DynamicObjectDescriptor) + sizeof(MemoryPageDescriptor), SYSTEMPAGESIZE - 2 * sizeof(DynamicObjectDescriptor) - sizeof(MemoryPageDescriptor), NULL, NULL};
				freePageListIndex->pmaStart += SYSTEMPAGESIZE;
				
				/*1.2.2 copy to location*/
				mmCopyData((byte*)(&dodNewPage), mpdNewPage.vmaStart, sizeof(DynamicObjectDescriptor), FALSE);
				mmCopyData((byte*)(&mpdNewPage), dodNewPage.start, sizeof(MemoryPageDescriptor), FALSE);
				mmCopyData((byte*)(&dodFreeArea), mpdNewPage.vmaStart + sizeof(DynamicObjectDescriptor) + sizeof(MemoryPageDescriptor), sizeof(DynamicObjectDescriptor), FALSE);
				
				/*1.2.3 link*/
				mmAppendDODToList((DynamicObjectDescriptor*)(mpdNewPage.vmaStart), &dodUsedListHead);
				mmAppendMPDToList((MemoryPageDescriptor*)(dodNewPage.start), &mpdUsedListHead);
				mmAppendDODToList((DynamicObjectDescriptor*)(dodNewPage.start + sizeof(MemoryPageDescriptor)), &dodFreeListHead);
				
				/*1.2.4 return*/
				return (MemoryPageDescriptor*)(dodNewPage.start);
			}
		}else{ /*free page not found*/
			freePageListIndex = freePageListIndex->next;
		}
	}while(freePageListIndex != NULL);
	
	return NULL;
}


public void mmCleanMPDFreeList(void){

	MemoryPageDescriptor* freeMPDIndex = mpdFreeListHead;
	MemoryPageDescriptor* freeMPDFirst = mpdFreeListHead;
	DynamicObjectDescriptor* dodForMPDIndex = NULL;

	if (freeMPDIndex == NULL) return; /*no need to clean*/
	if ((freeMPDIndex->prev == NULL) && (freeMPDIndex->next == NULL)) return; /*no need to clean as well*/
	
	do{
		if ((freeMPDIndex->pmaStart + 0x2000 * freeMPDIndex->size) == freeMPDFirst->pmaStart){ /*order index->first*/
		
			/*1.1A update first from index*/
			freeMPDFirst->pmaStart = freeMPDIndex->pmaStart;
		} else if ((freeMPDFirst->pmaStart + 0x2000 * freeMPDFirst->size) == freeMPDIndex->pmaStart){ /*order first->index*/
		
			/*1.1B do nothing and go to 1.2*/
		} else{
			freeMPDIndex = freeMPDIndex->next;
			continue;
		}
		/*1.2 update first mpd size*/
		freeMPDFirst->size += freeMPDIndex->size;
		
		/*1.3 remove mpd index from mpdFreeList*/
		mmRemoveMPDFromList(freeMPDIndex, &mpdFreeListHead);
		
		/*1.4 mark dod for index as free*/
		dodForMPDIndex = (DynamicObjectDescriptor*)((byte*)freeMPDIndex - sizeof(DynamicObjectDescriptor));
		
		/*1.5 remove dod for index from dodUsedList*/
		mmRemoveDODFromList(dodForMPDIndex, &dodUsedListHead);
		
		/*1.6 append dod for index to dodFreeList*/
		mmAppendDODToList(dodForMPDIndex, &dodFreeListHead);
		
		/*1.7 recursive call*/
		mmCleanMPDFreeList();
		
		return;

	}while(freeMPDIndex != NULL);
	
	return;
}

static sint8 mmSysPFree(MemoryPageDescriptor* mpd){
	
	DynamicObjectDescriptor* dodForMPD;
	DynamicObjectDescriptor* dodForFreeArea;
	
	if (mpd == NULL) return -1;
	
	/*1.1 decide if mpd is on the deleting page*/
	if (((uint32)(mpd->vmaStart) & 0xffffe000) == ((uint32)mpd & 0xffffe000)){ /*on-shore*/
	
		/*1A.2 check pre-requisitive*/
		dodForMPD = (DynamicObjectDescriptor*)(mpd->vmaStart);
		dodForFreeArea = (DynamicObjectDescriptor*)(mpd->vmaStart + sizeof(DynamicObjectDescriptor) + sizeof(MemoryPageDescriptor));
		if ((dodForFreeArea->size == (0x2000 - 2 * sizeof(DynamicObjectDescriptor) - sizeof(MemoryPageDescriptor))) && mmCheckDODFromList(dodForFreeArea, dodFreeListHead)){ /*all rest areas are cleared and free*/
		
			MemoryPageDescriptor* freeMPDIndex = mpdFreeListHead;
			DynamicObjectDescriptor* freeDODIndex = dodFreeListHead;
		
			/*1A.3 check if there are possible to merge with other free mpd on different page*/
			if (freeMPDIndex == NULL) return -4;
			do{
				if (((uint32)mpd & 0xffffe000) != ((uint32)freeMPDIndex & 0xffffe000)){
					if ((freeMPDIndex->pmaStart + 0x2000) == mpd->pmaStart){ /*order as index->mpd*/
						
						/*1A.3A.1 increase index size*/
						freeMPDIndex->size += 0x1;
						
						/*1A.3A.2 remove dodForFreeArea from dodFreeList*/
						mmRemoveDODFromList(dodForFreeArea, &dodFreeListHead);
						
						/*1A.3A.3 remove mpd from mpdUsedList*/
						mmRemoveMPDFromList(mpd, &mpdUsedListHead);
						
						/*1A.3A.4 remove dodForMPD from dodUsedList*/
						mmRemoveDODFromList(dodForMPD, &dodUsedListHead);
						
						mmCleanMPDFreeList();
						
						return 0;
					}else if ((mpd->pmaStart + 0x2000) == freeMPDIndex->pmaStart){ /*order as mpd->index*/
					
						/*1A.3B.1 reduce index->pmaStart and increase index->size by 0x2000*/
						freeMPDIndex->pmaStart -= 0x2000;
						freeMPDIndex->size += 0x1;
						
						/*1A.3B.2 remove dodForFreeArea from dodFreeList*/
						mmRemoveDODFromList(dodForFreeArea, &dodFreeListHead);
						
						/*1A.3B.3 remove mpd from mpdUsedList*/
						mmRemoveMPDFromList(mpd, &mpdUsedListHead);
						
						/*1A.3B.4 remove dodForMPD from dodUsedList*/
						mmRemoveDODFromList(dodForMPD, &dodUsedListHead);
						
						mmCleanMPDFreeList();
						
						return 0;
					}
				}
				freeMPDIndex = freeMPDIndex->next;
			}while(freeMPDIndex != NULL);
			
			/*1A.4 if not possible, check if there are spaces on other pages which can store this mpd+dod*/
			freeDODIndex = dodFreeListHead;
			
			if (freeDODIndex == NULL) return -4;
			do{
				if (((uint32)(freeDODIndex->start) & 0xffffe000) != ((uint32)(mpd->vmaStart) & 0xffffe000)){
					if (freeDODIndex->size == sizeof(MemoryPageDescriptor)){ /*perfect fit 1 mpd*/
					
						/*1A.4A.1 reuse mpd, update*/
						mpd->vmaStart = NULL;
						
						/*1A.4A.2 copy mpd to freeDODIndex->start*/
						mmCopyData((byte*)mpd, freeDODIndex->start, sizeof(MemoryPageDescriptor), FALSE);
					}else if (freeDODIndex->size >= (sizeof(MemoryPageDescriptor) + sizeof(DynamicObjectDescriptor))){ /*able to fit 1 mpd + 1 dod*/
					
						/*1A.4B.1 reuse mpd and dodForFreeArea, update*/
						mpd->vmaStart = NULL;
						dodForFreeArea->start = freeDODIndex->start + sizeof(MemoryPageDescriptor) + sizeof(DynamicObjectDescriptor);
						dodForFreeArea->size = freeDODIndex->size - sizeof(MemoryPageDescriptor) - sizeof(DynamicObjectDescriptor);
						freeDODIndex->size = sizeof(MemoryPageDescriptor);

						/*1A.4B.2 copy mpd + dodForFreeArea to freeDODIndex->start*/
						mmCopyData((byte*)mpd, freeDODIndex->start, sizeof(MemoryPageDescriptor) + sizeof(DynamicObjectDescriptor), FALSE);
						
						/*1A.4B.3 append copied dodForFreeArea to dodFreeListHead*/
						mmAppendDODToList((DynamicObjectDescriptor*)(freeDODIndex->start + sizeof(MemoryPageDescriptor)), &dodFreeListHead);
					}else{
						freeDODIndex = freeDODIndex->next;
						continue;
					}
					
					/*1A.4.2 remove freeDODIndex from dodFreeList*/
					mmRemoveDODFromList(freeDODIndex, &dodFreeListHead);
					
					/*1A.4.3 append freeDODIndex to dodUsedList*/
					mmAppendDODToList(freeDODIndex, &dodUsedListHead);
					
					/*1A.4.4 remove dodForFreeArea from dodFreeList*/
					mmRemoveDODFromList(dodForFreeArea, &dodFreeListHead);
					
					/*1A.4.5 remove dodMPD from dodUsedList*/
					mmRemoveDODFromList(dodForMPD, &dodUsedListHead);
					
					/*1A.4.6 remove mpd from mpdUsedList*/
					mmRemoveMPDFromList(mpd, &mpdUsedListHead);
					
					/*1A.4.7 append freeDODIndex->start to mpdFreeList*/
					mmAppendMPDToList((MemoryPageDescriptor*)(freeDODIndex->start), &mpdFreeListHead);
					
					mmCleanMPDFreeList();
					
					return 0;
				}
				freeDODIndex = freeDODIndex->next;
			}while(freeDODIndex != NULL);
			
			/*1A.5 not able to allocate a space to store deleting mpd*/
			return -5;

		}else{
			return -3; /*mpd can not be deleted*/
		}
	}else{/*off-shore*/
	
		/*1B.2 check pre-requisitive*/
		dodForMPD = (DynamicObjectDescriptor*)((byte*)mpd - sizeof(DynamicObjectDescriptor));
		dodForFreeArea = (DynamicObjectDescriptor*)(mpd->vmaStart);
		if ((dodForFreeArea->size == (0x2000 - sizeof(DynamicObjectDescriptor))) && mmCheckDODFromList(dodForFreeArea, dodFreeListHead)){ /*all rest area on deleting page is free*/
			
			/*1B.3 remove dodForFreeArea from dodFreeList*/
			mmRemoveDODFromList(dodForFreeArea, &dodFreeListHead);
			
			/*1B.4 remove mpd from mpdUsedList, mark as free*/
			mpd->vmaStart = NULL;
			mmRemoveMPDFromList(mpd, &mpdUsedListHead);
			
			/*1B.5 append mpd to mpdFreeList*/
			mmAppendMPDToList(mpd, &mpdFreeListHead);
			
			mmCleanMPDFreeList();
			
			return 0;
		}else{
			return -2; /*mpd can not be deleted since page still under using*/
		}
	}
	
	return -64; /*funny failed return*/
}

void* mmSysMAlloc(uint32 size){
	
	DynamicObjectDescriptor *freeDODIndex = dodFreeListHead;
	
	if (size == 0) return NULL;
	
	/*1.1 check if free dod list is empty, create a new page if needed or return as failed*/
	if (freeDODIndex == NULL){
		if (mmSysPAlloc() == NULL){
			return NULL;
		}
		freeDODIndex = dodFreeListHead;
	}
	
	/*1.2 parse all free dod nodes and get first usable slot*/
	do{
		if (freeDODIndex->size == size){ /*option 1: size perfect fit*/
			
			/*1.2A.2 remove freeDODIndex from dodFreeListHead*/
			mmRemoveDODFromList(freeDODIndex, &dodFreeListHead);
			
			/*1.2A.3 append freeDODIndex to dodUsedListHead*/
			mmAppendDODToList(freeDODIndex, &dodUsedListHead);
			
			/*1.2A.4 return freeDODIndex->start*/
			return (void*)(freeDODIndex->start);
			
		}else if(freeDODIndex->size >= (size + sizeof(DynamicObjectDescriptor))){ /*option 2: size can hold obj as well as 1 dod*/
		
			DynamicObjectDescriptor residualFreeDOD;
			
			/*1.2B.2 construct residual area with new free DOD*/
			residualFreeDOD.start = freeDODIndex->start + size + sizeof(DynamicObjectDescriptor);
			residualFreeDOD.size = freeDODIndex->size - size - sizeof(DynamicObjectDescriptor);
			residualFreeDOD.prev = NULL;
			residualFreeDOD.next = NULL;
			
			/*1.2B.3 update freeDODIndex size as needed size*/
			freeDODIndex->size = size;
			
			/*1.2B.4 copy new free DOD in location*/
			mmCopyData((byte*)(&residualFreeDOD), freeDODIndex->start + size, sizeof(DynamicObjectDescriptor), FALSE);
			
			/*1.2B.5 remove freeDODIndex from dodFreeListHead, append to dodUsedListHead*/
			mmRemoveDODFromList(freeDODIndex, &dodFreeListHead);
			mmAppendDODToList(freeDODIndex, &dodUsedListHead);
			
			/*1.2B.6 append new free DOD to dodFreeListHead*/
			mmAppendDODToList((DynamicObjectDescriptor*)(freeDODIndex->start + size), &dodFreeListHead);
			
			/*1.2B.7 return freeDODIndex->start*/
			return (void*)(freeDODIndex->start);
			
		}else{ /*option 3: looking for next one*/
			freeDODIndex = freeDODIndex->next;
		}
	}while(freeDODIndex != NULL);
	
	/*1.3 if there are no slots available, create a new page and try again*/
	if (mmSysPAlloc() == NULL){
			return NULL;
	}else{
		return mmSysMAlloc(size); /*recursive call*/
	}
	
	return NULL; /*will not execute*/
}

public void mmCleanDODFreeList(void){

	DynamicObjectDescriptor* dodFreeIndex = dodFreeListHead;
	DynamicObjectDescriptor* dodFreeFirst = dodFreeListHead;
	
	if (dodFreeIndex == NULL) return; /*no need to clean*/
	if ((dodFreeIndex->prev == NULL) && (dodFreeIndex->next == NULL)) return; /*no need to clean as well*/
	
	do{
		/*1.1 check pre-requisitive -> if they are on the same 8k page*/
		if (((uint32)dodFreeIndex & 0xffffe000) == ((uint32)dodFreeFirst & 0xffffe000)){ /*will only merge dod in same 8k page*/
			if (dodFreeIndex->start + dodFreeIndex->size + sizeof(DynamicObjectDescriptor)== dodFreeFirst->start){ /*order as index->first*/
			
				/*1.2A.1 remove dodFreeFirst from dodFreeListHead*/
				mmRemoveDODFromList(dodFreeFirst, &dodFreeListHead);
				
				/*1.2A.2 update dodFreeIndex as per dodFreeFirst*/
				dodFreeIndex->size += (dodFreeFirst->size + sizeof(DynamicObjectDescriptor));
				
				/*1.2A.3 remove then append dodFreeIndex to dodFreeListHead, since it will always go as the first node*/
				mmRemoveDODFromList(dodFreeIndex, &dodFreeListHead);
				mmAppendDODToList(dodFreeIndex, &dodFreeListHead);
				
				/*1.2A.4 recursive call*/
				mmCleanDODFreeList();
				
				return;
				
			}else if (dodFreeFirst->start + dodFreeFirst->size + sizeof(DynamicObjectDescriptor) == dodFreeIndex->start){ /*order as first->index*/
			
				/*1.2B.1 update dodFreeFirst size*/
				dodFreeFirst->size += (dodFreeIndex->size + sizeof(DynamicObjectDescriptor));
				
				/*1.2B.2 remove dodFreeIndex from dodFreeListHead*/
				mmRemoveDODFromList(dodFreeIndex, &dodFreeListHead);
				
				/*1.2B.3 recursive call*/
				mmCleanDODFreeList();
				
				return;
			}
		}
		
		dodFreeIndex = dodFreeIndex->next;
		
	}while(dodFreeIndex != NULL);

	return;
}

sint32 mmSysMFree(void* object){

	DynamicObjectDescriptor* dodForObject = NULL;
	DynamicObjectDescriptor* dodFirstFreeNode = NULL;

	if (object == NULL) return -1;
	
	dodForObject = (DynamicObjectDescriptor*)((byte*)object - sizeof(DynamicObjectDescriptor));
	
	/*1.2 remove dodForObject from dodUsedListHead*/
	mmRemoveDODFromList(dodForObject, &dodUsedListHead);
	
	/*1.3 append dodForObject to dodFreeListHead*/
	mmAppendDODToList(dodForObject, &dodFreeListHead);
	
	/*1.4 run mmCleanDODFreeList*/
	mmCleanDODFreeList();
	
	/*1.5 find possible empty page and delete*/
	dodFirstFreeNode = dodFreeListHead;
	if (dodFirstFreeNode == NULL) return -2;
	if (dodFirstFreeNode->size == (0x2000 - sizeof(DynamicObjectDescriptor))){ /*mpd off-shore*/
		MemoryPageDescriptor* mpdMatchIndex = mpdUsedListHead;
		if (mpdMatchIndex == NULL) return -3;
		do{
			if ((uint32)(mpdMatchIndex->vmaStart) == ((uint32)(dodFirstFreeNode->start) & 0xffffe000)){
				mmSysPFree(mpdMatchIndex);
				break;
			}
			mpdMatchIndex = mpdMatchIndex->next;
		}while(mpdMatchIndex != NULL);
	} else if (dodFirstFreeNode->size == (0x2000 - 2 * sizeof(DynamicObjectDescriptor) - sizeof(MemoryPageDescriptor))){ /*mpd on-shore*/
		MemoryPageDescriptor* mpdToDelete = (MemoryPageDescriptor*)(dodFirstFreeNode->start - sizeof(DynamicObjectDescriptor) - sizeof(MemoryPageDescriptor));
		mmSysPFree(mpdToDelete);
	}
	
	return 0;
}

